package main

import (
	"fmt"
	"sync"
)

// 数组栈，后进先出
type ArrayStack struct {
	array []string   //底层切片
	size  int        //栈的元素数量
	lock  sync.Mutex //并发安全使用锁
}

// 入栈
func (stack *ArrayStack) Push(v string) {
	stack.lock.Lock()
	defer stack.lock.Unlock()

	//放入切片中，后进的元素放在数组最后面
	stack.array = append(stack.array, v)

	//栈中元素的数量加1
	stack.size = stack.size + 1
}

//将元素入栈，会实现加锁实现安全并发
//入栈时直接把元素放在数组的最后面，然后元素数量加1.性能损耗主要花在切片追加元素上
//切片容量不够会自动扩容，底层损耗的复杂度这里不计，时间复杂度为O(1)

// 出栈
// 元素出栈，会先加锁实现并发安全
// 如果栈的大小为0,那么不允许出栈，否则从数组的最后面拿出元素
// 元素取出后
// 1 如果切片偏移量向前移动 stack.array[0:stack.size-1],表明最后的元素已经不属于该数组了
// 数组变相缩容了。此时，切片被缩容的部分不会被回收，仍然占据着空间，所以空间复杂度较高，但是操作的时间复杂度为:O(1)
// 2 如果我们创建新的数组newArray 然后把老数组的元素复制到新数组，就不会占用多余的空间，但移动次数过多，时间复杂度为:O(n)
func (stack *ArrayStack) Pop() string {
	stack.lock.Lock()
	defer stack.lock.Unlock()

	//栈中元素已空
	if stack.size == 0 {
		panic("empty")
	}
	//栈顶元素
	v := stack.array[stack.size-1]
	//创建新的数组，避免切片收缩占用空间变大
	newArray := make([]string, stack.size-1, stack.size-1)
	for i := 0; i < stack.size-1; i++ {
		newArray[i] = stack.array[i]
	}
	stack.array = newArray

	//栈中元素数量-1
	stack.size = stack.size - 1
	return v
}

// 获取栈顶元素
func (stack *ArrayStack) Peek() string {
	//栈中元素已空
	if stack.size == 0 {
		panic("empty")
	}

	// 栈顶元素值
	v := stack.array[stack.size-1]
	return v
}

// 获取栈大小和判断是否为空
// 栈大小
func (stack *ArrayStack) Size() int {
	return stack.size
}

// 栈是否为空
func (stack *ArrayStack) IsEmpty() bool {
	return stack.size == 0
}

func main() {
	arrayStack := new(ArrayStack)
	arrayStack.Push("hallo")
	arrayStack.Push("hi")
	arrayStack.Push("haha")
	arrayStack.Push("aad")
	fmt.Println(arrayStack.size)
	fmt.Println(arrayStack)
	arrayStack.Pop()
	fmt.Println(arrayStack)
}
